#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
#include<unordered_set>
#include<string>
#include<queue>
#include <sstream>

using namespace std;

set<string> nogram;
string headgram;

// 定义一个表示文法产生式的结构体
struct Gram {
    string left;  // 产生式的左部
    vector<string> right;  // 产生式的右部
};

//----------------------------------------------------------------------*******------------------

// 判断一个字符串是否是非终结符
bool isNonTerminal(const string& s) {
    return nogram.find(s) != nogram.end();
}

Gram mysplit(string str)
{
    string vleft;
    vector<string>vright;
    string temp = "";
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == '>' || str[i]== ' ')continue;
        if (str[i] == '-')
        {
            vleft = temp;
            temp = "";
            continue;
        }
        if (str[i] == '|')
        {
            vright.push_back(temp);
            temp = "";
            continue;
        }
        temp += str[i];
    }
    if (temp != "")vright.push_back(temp);
    nogram.insert(vleft);
    return Gram{ vleft,vright };
}

//输入文法
void getgrammar(vector<Gram>& v)
{
    printf("若一个非终结符可推出多个结果，请直接以 | 分隔，不必分开输入\n");
    printf("输入产生式,以$为结束标志:\n");
    string str;
    while (1)
    {
        getline(cin, str);
        if (str[0] == '$')
        {
            break;
        }
        v.push_back(mysplit(str));
    }
    headgram = v[0].left;
}

bool issame(const string& a, const string& b)
{
    if (a.length() < b.length())
    {
        return false;
    }
    return a.substr(0, b.length()) == b;
}

bool findnogram(string s)
{
    int n = s.length();
    for (int i = 0; i < n; i++)
    {
        string m(1, s[i]);
        if (nogram.find(m) != nogram.end())
        {
            return true;
        }
    }
    return false;
}

bool findA(string s,string A)
{
    int n = s.length();
    for (int i = 0; i < n; i++)
    {
        string m(1, s[i]);
        if (m == A)
        {
            return true;
        }
    }
    return false;
}

// 消除直接左递归的函数
void deleteDirLeft(vector<Gram>& grammar) {
    vector<Gram> newGrammar;

    for (size_t i = 0; i < grammar.size(); ++i) {
        string A = grammar[i].left;  // 当前非终结符
        vector<string> alpha, beta;

        // 将直接左递归的产生式分为 alpha（递归部分）和 beta（非递归部分）
        for (const auto& prod : grammar[i].right) {
            if (issame(prod,A)) {
                alpha.push_back(prod.substr(A.length()));  // 递归部分
            }
            else {
                beta.push_back(prod);  // 非递归部分
            }
        }

        // 如果 A 存在递归部分，进行直接左递归的消除
        if (!alpha.empty()) {
            string A_prime = A + "'";  // 新非终结符
            nogram.insert(A_prime);
            // 处理非递归部分
            for (auto& prod : beta) {
                prod += A_prime;
            }

            // 处理递归部分
            for (auto& prod : alpha) {
                prod += A_prime;
            }
            alpha.push_back("#");
            newGrammar.push_back({ A,beta });
            newGrammar.push_back({ A_prime,alpha });
        }
        else {
            newGrammar.push_back({ A, beta });
        }
    }

    // 更新原文法为消除左递归后的文法
    grammar = newGrammar;
}

// 消除间接左递归的函数
void deleteIndirLeft(vector<Gram>& grammar) {
    unordered_map<string, vector<string>> productions;
    vector<Gram> newGrammar;
    unordered_map<string, int> isused;

    // 将文法按非终结符分组
    for (const auto& g : grammar) {
        productions[g.left]=g.right;
        isused[g.left] = 0;
    }

    // 处理每个非终结符
    for (size_t i = 0; i < grammar.size(); ++i) {
        string A = grammar[i].left;  // 当前非终结符
        if (isused[A])
        {
            continue;
        }
        queue<string> alpha;
        vector<string> beta;

        queue<string> in;
        unordered_map<string, int> canA;
        //标记非终结符，哪些可以推导出A
        for (auto& g : grammar)
        {
            if (g.left == A)
            {
                continue;
            }
            in.push(g.left);
            canA[g.left] = -1;
        }

        int count = 0;//防止下面循环死锁
        while (!in.empty())
        {
            string inn = in.front();
            in.pop();
            int k = 0;
            for (auto& g : productions[inn])
            {
                for (int j = 0; j < g.length(); j++)
                {
                    string ew(1, g[j]);
                    if (ew == A)
                    {
                        k = 1;
                    }
                    else if(nogram.find(ew) != nogram.end())
                    {
                        if (canA[ew] == 1)
                        {
                            k = 1;
                        }
                        else if (canA[ew] == -1 && ew != inn)
                        {
                            k = -1;
                        }
                    }
                    if (k != 0)
                    {
                        break;
                    }
                }
                if (k != 0)
                {
                    break;
                }
            }
            if (k == 0)
            {
                canA[inn] = 0;
                count = 0;
            }
            else if (k == 1)
            {
                canA[inn] = 1;
                count = 0;
            }
            else
            {
                count++;
                if (count < grammar.size())
                {
                    in.push(inn);
                }
                else
                {
                    canA[inn] = 0;
                    count = 0;
                }
            }
        }

        // 遍历文法规则 A -> A1 | A2 | ...，消除间接左递归
        for (const auto& prod : productions[A]) {
            if (findnogram(prod)) {
                alpha.push(prod); // 递归部分
            }
            else {
                beta.push_back(prod);  // 非递归部分
            }
        }

        // 如果 A 存在递归部分，需要处理间接左递归
        while (!alpha.empty())
        {
            string m = alpha.front();
            alpha.pop();
            string ml = "", rl = "";
            string l = "";
            int log = 0;
            for (int i = 0; i < m.size(); i++)
            {
                string mm(1, m[i]);
                if (nogram.find(mm) != nogram.end() && mm!=A)
                {
                    if (canA[mm] == 1 && l == "")
                    {
                        log = 1;
                        l = mm;
                        continue;
                    }
                }
                if (log == 0)
                {
                    ml += mm;
                }
                else
                {
                    rl += mm;
                }
            }
            if (log == 0)
            {
                beta.push_back(m);
            }
            else
            {
                for (auto p : productions[l])
                {
                    alpha.push(ml + p + rl);
                }
            }
        }

        int check = 0;
        for (auto& b : beta)
        {
            if (findA(b, A))
            {
                check = 1;
                break;
            }
        }
        if (check)
        {
            for (auto u : canA)
            {
                if (u.second == 1)
                {
                    isused[u.first] = 1;
                }
            }
            newGrammar.push_back({ A,beta });
        }
        else
        {
            newGrammar.push_back({ A ,grammar[i].right });
        }
    }

    // 更新原文法为消除间接左递归后的文法
    grammar = newGrammar;
}

void printGram(vector<Gram> gram)
{
    cout << "文法：" << endl;
    for (auto& g : gram)
    {
        cout << g.left << " -> ";
        if (g.right.empty())
        {
            continue;
        }
        else
        {
            cout << g.right[0] << " ";
            if (g.right.size() > 1)
            {
                for (int i = 1; i < g.right.size(); i++)
                {
                    cout << "| " << g.right[i] << " ";
                }
            }
        }
        cout << endl;
    }
}

//----------------------------------------------------------------------*******------------------

// Trie树的节点结构
struct TrieNode {
    string father; // 该节点的字母
    vector<TrieNode*> children; // 孩子节点
    bool isEndOfWord = false; // 是否是一个完整单词的结尾

    TrieNode(string f) : father(f) {}
};

// Trie树类
class Trie {
public:
    TrieNode* root;
    string head;
    Trie() {
        root = new TrieNode("");
        head = "";
    }
    Trie(string A) {
        root = new TrieNode("");
        head = A;
    }
    // 插入一个单词到Trie树中
    void insert(const string& word) {
        TrieNode* node = root;
        for (int i = 0; i < word.size(); i++) {
            string c(1, word[i]);
            if (i + 1 < word.size() && word[i + 1] == '\'')
            {
                c += "'";
                i++;
            }
            bool found = false;
            for (auto& child : node->children) {
                if (child->father == c) {
                    node = child;
                    found = true;
                    break;
                }
            }
            if (!found) {
                TrieNode* newNode = new TrieNode(c);
                node->children.push_back(newNode);
                node = newNode;
            }
        }
        node->isEndOfWord = true;
    }
};

void showroot(TrieNode* p,const int n)
{
    cout << "| ";
    for (int i = 0; i < n; i++)
    {
        cout << "  ";
    }
    cout << "|__" << p->father << endl;
    for (auto& c : p->children)
    {
        showroot(c,n+1);
    }
}

void show(Trie trie)
{
    cout << trie.head << endl;
    TrieNode* p = trie.root;
    int i = 0;
    for (auto& c : p->children)
    {
        showroot(c, i);
    }
    cout << endl;
}

// 去除左公共因子的函数
void LeftFactor(vector<Gram>& grammar) {
    vector<Gram> newGrammar;

    for (auto& rule : grammar) {
        string A = rule.left;
        vector<string>& productions = rule.right;

        // 使用Trie树处理候选式
        Trie trie(A);
        for (const string& prod : productions) {
            trie.insert(prod);
        }
        show(trie);

        vector<string> str;
        vector<string> instr;
        string B = "'";
        while (nogram.find(A + B) != nogram.end())
        {
            B+="'";
        }
        for (auto c : trie.root->children)
        {
            TrieNode* p = c;
            string le = p->father;
            while (p!=NULL && p->children.size() == 1)
            {
                p = p->children[0];
                le += p->father;
            }
            if (p!=NULL && p->isEndOfWord)
            {
                instr.push_back(le);
            }
            else
            {
                str.push_back(le);
                instr.push_back(le + A + B);
                B += "'";
            }
        }

        newGrammar.push_back({ A,instr });
        for (int i=0;i<str.size();i++)
        {
            vector<string> newstr;
            for (const string& prod : productions) {
                if (issame(prod, str[i]))
                {
                    newstr.push_back(prod.substr(str[i].length()));
                }
            }
            string newA = A+"'";
            while (nogram.find(newA) != nogram.end())
            {
                newA += "'";
            }
            nogram.insert(newA);
            newGrammar.push_back({ newA, newstr });
        }
    }
    // 更新原文法
    grammar = newGrammar;
}

//----------------------------------------------------------------------*******------------------

class FirstFollow {
private:
    unordered_map<string, unordered_set<string>> first;  // 存储每个非终结符的 FIRST 集
    unordered_map<string, unordered_set<string>> follow;  // 存储每个非终结符的 FOLLOW 集
    unordered_map<string, vector<string>> grammar;  // 存储文法规则

public:
    // 添加文法规则
    void addRule(const vector<Gram>& gram) {
        for (auto& g : gram)
        {
            grammar[g.left] = g.right;
        }
    }

    // 计算 FIRST 集
    void computeFirst() {
        bool changed = true;

        // 初始化 FIRST 集
        for (const auto& rule : grammar) {
            first[rule.first];  // 确保每个非终结符都有一个空的 FIRST 集
        }

        while (changed) {
            changed = false;

            // 遍历所有产生式
            for (const auto& rule : grammar) {
                const string& nonTerminal = rule.first;
                const vector<string>& productions = rule.second;

                for (const string& prod : productions) {
                    size_t i = 0;
                    bool epsilonFound = true;

                    while (i < prod.size()) {
                        string symbol(1, prod[i]);
                        while (i + 1 < prod.size())
                        {
                            string c(1, prod[i + 1]);
                            if (c == "'")
                            {
                                symbol += c;
                                i++;
                            }
                            else
                            {
                                break;
                            }
                        }


                        if (isTerminal(symbol)) {
                            // 如果是终结符，加入到 FIRST 集
                            if (first[nonTerminal].find(symbol) == first[nonTerminal].end()) {
                                first[nonTerminal].insert(symbol);
                                changed = true;
                            }
                            epsilonFound = false;
                            break;
                        }
                        else {
                            // 如果是非终结符，加入其 FIRST 集
                            for (const string& item : first[symbol]) {
                                if (first[nonTerminal].find(item) == first[nonTerminal].end()) {
                                    if (item == "#") continue;
                                    first[nonTerminal].insert(item);
                                    changed = true;
                                }
                            }

                            // 如果下一个非终结符能推导出空串(#)，继续查看后续符号
                            if (first[symbol].find("#") == first[symbol].end()) {
                                epsilonFound = false;
                                break;
                            }
                        }
                        i++;
                    }

                    // 如果整个右部可以推导出空串, 将 # 添加到 FIRST 集
                    if (epsilonFound && first[nonTerminal].find("#") == first[nonTerminal].end()) {
                        first[nonTerminal].insert("#");
                        changed = true;
                    }
                }
            }
        }
    }

    // 计算 FOLLOW 集
    void computeFollow() {
        follow[headgram].insert("$");  // 将起始符号的 FOLLOW 集初始化为 { $ }

        bool changed = true;

        while (changed) {
            changed = false;

            // 遍历所有产生式
            for (const auto& rule : grammar) {
                const string& nonTerminal = rule.first;
                const vector<string>& productions = rule.second;

                for (const string& prod : productions) {
                    for (size_t i = 0; i < prod.size(); ++i) {
                        string symbol(1, prod[i]);
                        while (i + 1 < prod.size())
                        {
                            string c(1, prod[i + 1]);
                            if (c == "'")
                            {
                                symbol += c;
                                i++;
                            }
                            else
                            {
                                break;
                            }
                        }

                        if (!isTerminal(symbol)) {
                            // 如果是非终结符
                            if (i + 1 < prod.size()) {
                                string nextSymbol(1, prod[i + 1]);

                                if (isTerminal(nextSymbol)) {
                                    if (follow[symbol].find(nextSymbol) == follow[symbol].end()) {
                                        follow[symbol].insert(nextSymbol);
                                        changed = true;
                                    }
                                }
                                else {
                                    for (const string& item : first[nextSymbol]) {
                                        if (item != "#" && follow[symbol].find(item) == follow[symbol].end()) {
                                            follow[symbol].insert(item);
                                            changed = true;
                                        }
                                    }

                                    // 如果下一个符号的 FIRST 集包含 #, 就将 FOLLOW 集的内容传递过来
                                    if (first[nextSymbol].find("#") != first[nextSymbol].end()) {
                                        for (const string& item : follow[nonTerminal]) {
                                            if (follow[symbol].find(item) == follow[symbol].end()) {
                                                follow[symbol].insert(item);
                                                changed = true;
                                            }
                                        }
                                    }
                                }
                            }
                            else {
                                // 如果是最后一个符号，传递 FOLLOW 集
                                for (const string& item : follow[nonTerminal]) {
                                    if (follow[symbol].find(item) == follow[symbol].end()) {
                                        follow[symbol].insert(item);
                                        changed = true;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    // 输出 FIRST 集
    void printFirst() {
        cout << "FIRST 集：" << endl;
        for (const auto& entry : first) {
            cout << entry.first << ": { ";
            for (const auto& symbol : entry.second) {
                cout << symbol << " ";
            }
            cout << "}" << endl;
        }
    }

    // 输出 FOLLOW 集
    void printFollow() {
        cout << "FOLLOW 集：" << endl;
        for (const auto& entry : follow) {
            cout << entry.first << ": { ";
            for (const auto& symbol : entry.second) {
                cout << symbol << " ";
            }
            cout << "}" << endl;
        }
    }

private:
    bool isTerminal(const string& symbol) {
        return nogram.find(symbol) == nogram.end(); // 假设终结符是小写字母
    }
};

//----------------------------------------------------------------------*******------------------

int main() {
    // 输入文法
    vector<Gram> grammar;
    getgrammar(grammar);

    //消除左递归
    deleteIndirLeft(grammar);//间接
    //消除左递归
    deleteDirLeft(grammar);//直接 
    printGram(grammar);

    //左公共因子提取
    LeftFactor(grammar);
    printGram(grammar);

   //FIRST集和FOLLOW集
    FirstFollow ff;
    ff.addRule(grammar);

    // 计算 FIRST 和 FOLLOW 集
    ff.computeFirst();
    ff.computeFollow();
    // 输出结果
    ff.printFirst();
    ff.printFollow();

    return 0;
}
